Leetcode-22:Generate Parentheses

2018-01-04

问题描述：

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

问题示例

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

我的答案

//#wrong# 以为n = ()+[n-1];([n-1]);[n-1]+() 
vector<string> generateParenthesis(int n) {
    vector<string> output;
    set<string> stringset1; //set用于去重
    set<string> stringset2;
    string temp="";
    stringset1.insert(temp);
    for(int i=0;i<n;i++){
        while (!stringset1.empty()) {
            temp = *stringset1.begin();
            stringset1.erase(*stringset1.begin());
            stringset2.insert("("+temp+")");
            stringset2.insert("()"+temp);
            stringset2.insert(temp+"()");
        }
        swap(stringset1, stringset2);
    }
    while (!stringset1.empty()) {
        output.push_back(*stringset1.begin());
        stringset1.erase(*stringset1.begin());
    }
    return output;
}
//#right#--TimeLimit
vector<string> generateParenthesis(int n) {
    vector<string> output;
    set<string> string1;
    set<string> string2;
    vector<int> start;
    vector<int> end;
    stack<char> stack;
    string add = "";
    string out = "";
    if(n == 0){
        return output;
    }
    string1.insert("()");
    for(int i=1;i<n;i++){
        while (!string1.empty()) {
            add = *string1.begin();
            string1.erase(add);
            for(int j=0;j<add.length();j++){
                if(stack.empty()){
                    start.push_back(j);
                    stack.push('(');
                }else{
                    if(add[j] == ')'){
                        stack.pop();
                        if(stack.empty()){
                            end.push_back(j);
                        }
                    }else{
                        stack.push('(');
                    }
                }
            }
            //组合开始结束下标，拼成新的string
            for (int i=0; i<start.size(); i++) {
                for (int j=0; j<end.size(); j++) {
                    if(start[i]<=end[j]){
                        if(start[i]>0&&end[j]+1<add.length()-1){
                            out = add.substr(0,start[i]) + '(' + add.substr(start[i],end[j]-start[i]+1) + ')' + add.substr(end[j]+1,add.length()-end[j] -1);
                        }else if(start[i] == 0){
                            out = '(' + add.substr(start[i],end[j]-start[i]+1) + ')' + add.substr(end[j]+1,add.length()-end[j] -1);
                        }else{
                            out = add.substr(0,start[i]) + '(' + add.substr(start[i],end[j]-start[i]+1) + ')';
                        }
                        string2.insert(out);
                    }
                }
            }
            string2.insert("()"+add);
            string2.insert(add+"()");
        }
        swap(string1, string2);
    }
    while (!string1.empty()) {
        output.push_back(*string1.begin());
        string1.erase(*string1.begin());
    }
    return output;
}
//#right#--Advanced AC
vector<string> generateParenthesis(int n) {
    stack<char> total;
    vector<string> output;
    set<string> string1;
    set<string> string2;
    stack<char> stack;
    string add = "";
    string out = "";
    if(n == 0){
        return output;
    }
    string1.insert("()");
    for(int i=1;i<n;i++){
        while (!string1.empty()) {
            add = *string1.begin();
            string1.erase(add);
            for(int j=0;j<add.length();j++){
                if(total.empty()){
                    stack.push('(');
                    total.push('(');
                    if(j>0){
                        string2.insert(add.substr(0,j) + "()" + add.substr(j,add.length()-j+1));
                    }else{
                        string2.insert("()"+add);
                    }
                    for(int k=j+1;k<add.length();k++){
                        if(add[k] == ')'){
                            stack.pop();
                        }else{
                            stack.push('(');
                        }
                        if(stack.empty()){
                            if(j>0&&k+1<add.length()-1){
                                out = add.substr(0,j) + '(' + add.substr(j,k-j+1) + ')' + add.substr(k+1,add.length()-k -1);
                            }else if(j == 0){
                                out = '(' + add.substr(j,k-j+1) + ')' + add.substr(k+1,add.length()-k -1);
                            }else{
                                out = add.substr(0,j) + '(' + add.substr(j,k-j+1) + ')';
                            }
                            string2.insert(out);
                        }
                    }
                    string2.insert(add+"()");
                }else{
                    if(add[j] == ')'){
                        total.pop();
                    }else{
                        total.push('(');
                    }
                }
            }
        }
        swap(string1, string2);
    }
    while (!string1.empty()) {
        output.push_back(*string1.begin());
        string1.erase(*string1.begin());
    }
    return output;
}

其他高效答案

vector<string> generateParenthesis(int n) {
        vector<string> ans;
        backtracking(ans, "", 0, 0, n);
        return ans;        
    }
private:
    void backtracking(vector<string>& ans, string s, int l, int r, int n) {
        if (l < n)
            backtracking(ans, s + "(", l + 1, r, n);
        if (r < l)
            backtracking(ans, s + ")", l, r + 1, n);
        else if (r == l && l == n)
            ans.push_back(s);
        return;
    }

参考文献

该问题解的个数就是卡特兰数，但是现在不是求个数，而是要将所有合法的括号排列打印出来。

该问题和《编程之美》的买票找零问题一样，通过买票找零问题我们可以知道，针对一个长度为2n的合法排列，第1到2n个位置都满足如下规则：左括号的个数大于等于右括号的个数。所以，我们就可以按照这个规则去打印括号：假设在位置k我们还剩余left个左括号和right个右括号，如果left>0，则我们可以直接打印左括号，而不违背规则。能否打印右括号，我们还必须验证left和right的值是否满足规则，如果left>=right，则我们不能打印右括号，因为打印会违背合法排列的规则，否则可以打印右括号。如果left和right均为零，则说明我们已经完成一个合法排列，可以将其打印出来。通过深搜，我们可以很快地解决问题

//左括号数必然大于等于右括号数
void generate(int leftNum,int rightNum,string s,vector<string> &result)  
    {  
        if(leftNum==0&&rightNum==0)  
        {  
            result.push_back(s);  
        }  
        if(leftNum>0)  
        {  
            generate(leftNum-1,rightNum,s+'(',result);  
        }  
        if(rightNum>0&&leftNum<rightNum)  
        {  
            generate(leftNum,rightNum-1,s+')',result);  
        }  
}
 
资料来源:<http://blog.csdn.net/yutianzuijin/article/details/13161721>